/**
 * 堆调整算法
 * @param {*} r 堆
 * @param {*} k 堆顶
 * @param {*} m 堆底
 */
function sift (r, k, m) {
    let i = k, j = 2*i, x = r[k], finished = false, t = r[k]
    while (j <= m & !finished) {
        if (j < m & r[j] > r[j + 1]) { 
            j = j + 1
        }
        if (x <= r[j]) {
            finished = true
        } else {
            r[i] = r[j]
            i = j
            j = i * 2
        }
    }
    r[i] = t
}

function heapSort (r) {
    let n = r.length
    // 将无序的序列创建成堆
    for (let i = Math.floor((n - 1) / 2); i >= 0; i--) {
        sift(r, i, n)
    }
    console.log(r);
    
    // 使用堆排序
    for (let i = n - 1; i > 0; i--) {
        let tmp = r[0]
        r[0] = r[i]
        r[i] = tmp
        sift(r, 0, i - 1)
    }
    console.log(r);
}

heapSort([1, 30, 3, 69, 23, 96])